#include "Builder_Agglomerative.h"
#include <cfloat>

Builder_Agglomerative::
Builder_Agglomerative(Cluster_Metric metric) {
    this->metric = metric;
}

~Builder_Agglomerative::Builder_Agglomerative() {
    reset();
}

// Here, we build a tree from the bottom up.
// The argument passed (a cluster) is treated as a set
// of objects, to be joined into ever-larger clusters.

void Builder_Agglomerative::build(Cluster& original_set) {
    Object_List items;

    // The algorithm used is brute-force, and runs in O(N^3*H^2) time!
    // Initially, we have a set of N singleton clusters.
    // Then, repeat N-1 times:
    // Find the clusters A and B in the set, which are closest.
    // Join them into a parent cluster C,
    // remove them from the set,
    // and insert C into the set.

    reset();
    for (LMO_Iterator iter = original_set.start;
         iter != original_set.end; iter++) {
        Labeled_Metric_Object *p = *iter;
        LMO_Iterator next = iter;
        next++;
        Cluster *c = new Cluster(iter, next, 1, Color::Black);
        active_clusters.push_back(c);
        items.append(c);
    }

    // Pass through the list of clusters N-1 times.
    for (int i_pass = 0; i_pass < items.n - 1; i_pass++) {

        // Find the closest two in the list.
        double min_distance = FLT_MAX;
        list<Cluster*>::iterator best_A;
        list<Cluster*>::iterator best_B;
        Cluster *A;
        Cluster *B;
        for (list<Cluster*>::iterator iter = active_clusters.begin();
             iter != active_clusters.end(); iter++) {
            A = *iter;

            list<Cluster*>::iterator jter = iter;
            jter++;
            for (; jter != active_clusters.end(); jter++) {
                B = *jter;
                double distance = metric.distance(A, B);
                if (distance < min_distance) {
                    best_A = iter;
                    best_B = jter;
                    min_distance = distance;
                }
            }
        }

        // Merge the two closest into one parent.
        A = *best_A;
        B = *best_B;
        Cluster *parent = new Cluster(A->span, Color::BLACK);
        parent->append(items, B);

        // Update the tree of clusters to reflect the change.
        tree.make_family(parent, A, B);

        // And update the active list
        active_list.erase(best_A);
        active_list.erase(best_B);
        active_list.push_back(parent);
    }
}

void Builder_Agglomerative::reset() {
    tree.destroy();
    for (list<Cluster*>::iterator iter = active_clusters.begin();
         iter != active_clusters.end(); iter++) {
        delete *iter;
    }
    active_clusters.clear();
}
